#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<unordered_map>
#include<functional>
#include<unordered_set>
using namespace std;
//stack<int> st;
//bool Caculation(string& s)
//{
//	auto x = st.top();
//	st.pop();
//	if (st.empty())
//	{
//		cout << "Expression Error: " << x << endl;
//		return false;
//	}
//	auto y = st.top();
//	st.pop();
//	if (s == "+")
//		st.push(x + y);
//	else if (s == "-")
//		st.push(y - x);
//	else if (s == "*")
//		st.push(x * y);
//	else if (s == "/")
//	{
//		if (x == 0)
//		{
//			cout << "Error: " << y << "/0" << endl;
//			return false;
//		}
//		st.push(y / x);
//	}
//	return true;
//}
//int main()
//{
//	string s;
//	while ((cin >> s) && s != "#")
//	{
//		if (s == "+" || s == "-" || s == "*" || s == "/")
//		{
//			bool ret = Caculation(s);
//			if (ret == false)
//				return 0;
//		}
//		else
//			st.push(stoi(s));
//	}
//	if (st.size() > 1)
//		cout << "Expression Error: " << st.top() << endl;
//	else
//		cout << st.top() << endl;
//	return 0;
//}
//int n, m, k;
//bool Judge(vector<int>& v)
//{
//	stack<int> st;
//	int popi = 1;
//	for (auto& e : v)
//	{
//		st.push(e);
//		while (!st.empty()&&st.top() == popi)
//		{
//			st.pop();
//			popi++;
//		}
//		if (st.size() > m)
//			return false;
//	}
//	return st.empty();
//}
//int main()
//{
//	cin >> n >> m >> k;
//	while (k--)
//	{
//		vector<int> v(n);
//		for (auto& e : v)
//			cin >> e;
//		if (Judge(v))
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	}
//	return 0;
//}
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> A, B;
//	for (int i = 0; i < n; i++)
//	{
//		int tmp;
//		cin >> tmp;
//		if (tmp % 2 == 1)
//			A.push_back(tmp);
//		else
//			B.push_back(tmp);
//	}
//	int i = 0, j = 0;
//	int sza = A.size(), szb = B.size();
//	while (i < sza && j < szb)
//	{
//		cout << A[i++] << " ";
//		if(i < sza)
//			cout << A[i++] << " ";
//		cout << B[j++] << " ";
//	}
//	while (i < sza)
//	{
//		if (i == sza - 1)
//		{
//			cout << A[i++];
//			break;
//		}
//		cout << A[i++] << " ";
//	}
//	while (j < szb)
//	{
//		if (j == szb - 1)
//		{
//			cout << B[j++];
//			break;
//		}
//		cout << B[j++] << " ";
//	}
//	return 0;
//}

//int main()
//{
//	int n;
//	cin >> n;
//	vector<vector<int>> maze(n, vector<int>(n));
//	for (int i = 0; i < n; i++)
//		for (int j = 0; j < n; j++)
//			cin >> maze[i][j];
//	int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
//	vector<vector<bool>> visited(n, vector<bool>(n,false));
//	vector<pair<int,int>> ret;
//	function<bool(int,int)> dfs = [&](int i,int j)->bool
//	{
//		ret.push_back({ i,j });
//		visited[i][j] = true;
//		if (i == n - 2 && j == n - 2)
//			return true;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && y >= 0 && x < n && y < n 
//				&& maze[x][y] == 0 && visited[x][y]==false)
//			{
//				if (dfs(x, y))
//					return true;
//				ret.pop_back();
//				visited[x][y] = false;
//			}
//		}
//		return false;
//	};
//	if (dfs(1, 1) == false)
//		cout << "NO" << endl;
//	else
//	{
//		for (auto& [x, y] : ret)
//			cout << "(" << x << "," << y << ")";
//	}
//	return 0;
//}
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	while (n--)
//	{
//		string s;
//		cin >> s;
//		int counts = 0;
//		for (auto& e : s)
//		{
//			if (e == 'S')
//				counts++;
//			else
//			{
//				if (counts-- == 0)
//				{
//					cout << "NO" << endl;
//					goto next;
//				}
//			}
//			if (counts > m)
//			{
//				cout << "NO" << endl;
//				goto next;
//			}
//		}
//		if(counts==0)
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	next:
//		;
//	}
//	return 0;
//}
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
	unordered_map<string, vector<string>> graph;
	unordered_map<string, int> in;
	int n = recipes.size();
	for (int i = 0; i < n; i++)
	{
		for (auto& s : ingredients[i])
			graph[s].push_back(recipes[i]);
		in[recipes[i]] = ingredients[i].size();
	}
	queue<string> q;
	for (auto& s : supplies)
	{
		q.push(s);
	}
	unordered_set<string> visited;
	while (!q.empty())
	{
		auto s = q.front();
		q.pop();
		visited.insert(s);
		for (auto& e : graph[s])
		{
			in[e]--;
			if (in[e] == 0 && !visited.count(e))
			{
				q.push(e);
			}
		}
	}
	vector<string> ret;
	for (int i = 0; i < n; i++)
	{
		if (visited.count(recipes[i]))
			ret.push_back(recipes[i]);
	}
	return ret;
}